package com.hardy.leetcode;

import java.util.ArrayList;

/**
 * User: Ruijie Date: 2016/9/20
 */
public class Combinations {
    public static ArrayList<ArrayList<Integer>> combine(int n, int k) {
        if(n<1){
            return null;
        }
        int[] arr=new int[n];
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<n;i++){
            arr[i]=i+1;
        }
        dfs(arr,0,res,new ArrayList<Integer>(),k);
        return res;
    }

    private static void dfs(int[] arr, int start, ArrayList<ArrayList<Integer>> res,
                            ArrayList<Integer> array, int k) {
        if(array.size()==k){
            res.add(new ArrayList<>(array));
        }
        for(int i=start;i<arr.length;i++){
            array.add(arr[i]);
            dfs(arr,i+1,res,array,k);
            array.remove(array.size()-1);
        }
    }

    public static void main(String[] args) {
        System.out.println(combine(4,2));
    }
}
